package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.LinkedList;

/**
 * @author qidi
 * @date 2022-01-12 09:39:39
 */
class Q0129_SumRootToLeafNumbers {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int sum;
        LinkedList<Integer> cur;

        public int sumNumbers(TreeNode root) {
            sum = 0;
            cur = new LinkedList<>();
            cur.add(root.val);
            process(root);
            return sum;
        }

        private void process(TreeNode node) {
            if (node.left == null && node.right == null) {
                for (int i = 0; i < cur.size(); i++) {
                    sum += cur.get(i) * Math.pow(10, i);
                }
                return;
            }

            if (node.left != null) {
                cur.addFirst(node.left.val);
                process(node.left);
                cur.removeFirst();
            }

            if (node.right != null) {
                cur.addFirst(node.right.val);
                process(node.right);
                cur.removeFirst();
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0129_SumRootToLeafNumbers().new Solution();
        BTreeUtil instance = BTreeUtil.getInstance();
        System.out.println(solution.sumNumbers(instance.generateFromArray(1, 2, 3)));
        System.out.println(solution.sumNumbers(instance.generateFromArray(4, 9, 0, null, 1)));
    }
}